package com.rran.study.algorithm.easy.day01;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author yy
 * @Type Solution02.java
 * @Desc 优解 巧妙运用队列
 * @date 2020/9/3
 */
public class Solution02 {
    public static void main(String[] args) {
        Solution02 solution = new Solution02();
        TreeNode t0 = new TreeNode(2147483647);
        TreeNode t1 = new TreeNode(2147483647);
        TreeNode t2 = new TreeNode(2147483647);
        TreeNode t3 = new TreeNode(15);
        TreeNode t4 = new TreeNode(7);
        t0.setLeft(t1);
        t0.setRight(t2);
//        t2.setLeft(t3);
//        t2.setRight(t4);
        List<Double> result = solution.averageOfLevels(t0);
        double[] array = new double[result.size()];

        //打印结果
        for (Double d : result) {
            System.out.println(d);
        }
    }

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (list.size() != 0){
            int len = list.size();
            double sum = 0;
            for (int i = 0; i < len; i++){
                TreeNode node = list.poll();
                sum += node.getVal();
                if (node.getLeft() != null) {
                    list.add(node.getLeft());
                }
                if (node.getRight() != null) {
                    list.add(node.getRight());
                }
            }
            res.add(sum/len);
        }
        return res;
    }

}


